package problems.contest;

/**
 * @author dubulingbo, 2023/4/1 10:40.
 */
public class WCT338 {

    // T2
    public boolean primeSubOperation(int[] nums) {
        int n = nums.length;

        // 建立质数表
        // true - 非质数
        // false 质数
        boolean[] nonPrime = new boolean[1000];

        for (int i = 2; i * i < 1000; ++i) {
            for (int j = i + i; j < 1000; j += i) {
                nonPrime[j] = true;
            }
        }

        // 最右边未选择的下标
        int pre = 0;
        for (int i = 1; i < n; ++i) {
            if (nums[i] > nums[i - 1]) continue;
            // 从最左边开始减少
            while (pre < i) {
                // nums[pre] 从最小值开始枚举
                int k = pre == 0 ? 1 : nums[pre - 1] + 1;
                int min = Math.min(nums[pre], nums[pre + 1]);
                while (k < min && nonPrime[nums[pre] - k]) {
                    ++k;
                }
                if (k >= nums[pre + 1]) return false;
                nums[pre++] = k;
            }
        }

        return true;
    }

    private boolean isPrime(int k) {
        if (k < 2) return false;

        int q = (int) Math.sqrt(k);

        for (int i = 2; i <= q; ++i) {
            if (k % i == 0) return false;
        }
        return true;
    }


    public static void main(String[] args) {
        WCT338 test = new WCT338();
        System.out.println(test.primeSubOperation(new int[]{2, 318, 42}));
        System.out.println(test.primeSubOperation(new int[]{16, 8, 4}));
        System.out.println(test.primeSubOperation(new int[]{4, 9, 6, 10}));
    }

}
